/**
 * 
 */
package tree.passed;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author xyyi
 *
 */
public class BinaryTreeLevelOrderTraversal {

	/**
	Binary Tree Level Order Traversal
	Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

	For example:
	Given binary tree {3,9,20,#,#,15,7},

	3
	/ \
	9  20
	/  \
	15   7
	return its level order traversal as:

	[
	[3],
	[9,20],
	[15,7]
	]
	 */
	/*
	 * Time O(n), n is the number of node in this tree
	 */
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

		ArrayList<ArrayList<Integer>> levelList = new ArrayList<ArrayList<Integer>>();
		if (root == null)
			return levelList;

		ArrayList<Integer> level = new ArrayList<Integer>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		queue.offer(null);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node != null) {
				level.add(node.val);
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			} else {
				levelList.add(new ArrayList<Integer>(level));
				level.clear();
				if (!queue.isEmpty())
					queue.offer(null);
			}
		}

		return levelList;
	}

	/*
	 * http://leetcode.com/2010/09/binary-tree-level-order-traversal-using_17.html
	 * 
	 * Time O(n), n is the number of node in this tree
	 */
	public ArrayList<ArrayList<Integer>> levelOrderDFS(TreeNode root) {

		ArrayList<ArrayList<Integer>> levelNodes = new ArrayList<ArrayList<Integer>>();
		int height = getHeight(root);
		for (int level = 1; level <= height; level++) {
			ArrayList<Integer> nodes = new ArrayList<Integer>();
			getLevel(root, level, nodes);
			levelNodes.add(nodes);
		}

		return levelNodes;
	}

	private int getHeight(TreeNode root) {
		if (root == null)
			return 0;

		int left = getHeight(root.left);
		int right = getHeight(root.right);
		return Math.max(left, right) + 1;
	}

	private void getLevel(TreeNode root, int level, ArrayList<Integer> nodes) {
		assert (level >= 1 && nodes != null);
		if (root == null)
			return;
		if (level == 1) {
			nodes.add(root.val);
		} else {
			getLevel(root.left, level - 1, nodes);
			getLevel(root.right, level - 1, nodes);
		}
	}

	/**
	Binary Tree Level Order Traversal II
	Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

	For example:
	Given binary tree {3,9,20,#,#,15,7},

	3
	/ \
	9  20
	/  \
	15   7
	return its bottom-up level order traversal as:

	[
	[15,7]
	[9,20],
	[3],
	]
	 */
	public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
		ArrayList<ArrayList<Integer>> levelList = new ArrayList<ArrayList<Integer>>();
		if (root == null) {
			return levelList;
		}

		LinkedList<ArrayList<Integer>> linkedList = new LinkedList<ArrayList<Integer>>();
		ArrayList<Integer> level = new ArrayList<Integer>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		queue.add(null);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node != null) {
				level.add(node.val);
				if (node.left != null)
					queue.add(node.left);
				if (node.right != null)
					queue.add(node.right);
			} else {
				linkedList.addFirst(new ArrayList<Integer>(level));
				level.clear();
				if (!queue.isEmpty()) {
					queue.add(null);
				}
			}
		}

		levelList.addAll(linkedList);
		return levelList;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public BinaryTreeLevelOrderTraversal() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
